package lc20240528;

import lc20240526.ListNode;

/**
 * @author WangCheng帅哥
 * @version 1.0
 * @description: k个一组反转链表
 * @date 2024/5/28
 */
public class ReverseList2 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

        ListNode newHead = reverseKGroup(head, 2);
        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
    }

    //遍历链表，分组处理。
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prevGroupEnd = dummy;
        ListNode curr = head;

        while (curr != null) {
            // 找到 k 个节点
            ListNode groupStart = curr;
            int count = 0;
            while (curr != null && count < k) {
                curr = curr.next;
                count++;
            }

            // 如果节点数不足 k 个，不需要反转
            if (count < k) {
                break;
            }

            // 反转 k 个节点
            ListNode prev = null;
            ListNode next = null;
            ListNode node = groupStart;
            for (int i = 0; i < k; i++) {
                next = node.next;
                node.next = prev;
                prev = node;
                node = next;
            }

            // 连接反转后的部分
            prevGroupEnd.next = prev;
            groupStart.next = curr;
            prevGroupEnd = groupStart;
        }
        return dummy.next;
    }
}
